This invention relates to communications over a computer network, and more particularly to the use of timing events to detect loss of a frame.
When a frame is transmitted over a computer network there is a possibility that it will be lost. Loss of a frame can be due to a number of factors. The factors include: failure of an intermediate link; congestion in the network; failure of a bridge or router; aborted frames in the network; cyclic redundancy check (CRC) errors; etc. In order to compensate for lost frames during transmission from a source station to a destination station, over a computer network, it is a common practice to transmit an acknowledge message (ACK message) by the destination station upon receipt of an information frame, or a sequence of frames. The ACK message usually gives the sequence number of the last correctly received frame, and may be either a separate short frame or may be xe2x80x9cpiggybackedxe2x80x9d on an information frame traveling upstream from the destination station to the source station.
Also, an acknowledgment timer (ACK timer) is operated in the source station. The ACK timer is started when the frame is transmitted onto the network (usually at the beginning of the transmission). In the event that an ACK message is not received before the expiration of the ACK timer, then it is a common practice to have the source station either retransmit the information frame, or depending upon the protocol, transmit a poll frame to the destination station. The destination station, upon receipt of the poll frame, is required to transmit a response to the source station. The purpose of the poll frame and the response frame is for the source station to learn: whether or not the destination station is still operative on the network; if the route in a source route bridged (SRB) network is still operative; retrieving the sequence number of the last correctly received frame; etc.
A problem with operating an ACK timer in the source station is that delays in the network can cause the ACK timer to expire before the source station receives an acknowledgment frame from the destination station.
Logical Link Control Layer (LLC) reliable communication was introduced; and sequence numbers for frames along with acknowledgment (ACK) messages permit establishment of reliable communication in layer 2 of the OSI communications reference model. LLC reliable communication is referred to as xe2x80x9cLLC type 2xe2x80x9d reliable communication. When introduced, LLC type 2 reliable communication was established between end stations on IEEE 802.5 token ring networks, and their extension with bridges to source route bridged (SRB) networks. A fixed time timing interval for ACK messages was appropriate for uncongested small SRB networks. Later, introduction of wide area network (WAN) links in SRB networks along with development of congestion problems at bridges in SRB networks lengthened the packet travel time in the networks, and lead to time-out problems in the ACK timer.
In LLC type 2 reliable communication the source station inserts a sequence number in a field of the LLC type 2 header (in an exemplary version of the IEEE standard three (3) bits are designated for the sequence number, in another exemplary version of the IEEE standard seven (7) bits are designated for the sequence number). In some point-to-point protocols the LLC TYPE 2 function in the LLC layer can read the sequence numbers of received packets, and can request retransmission of packets which are missing. The LLC TYPE 2 fields of a frame are fully disclosed by Radia Perlman in her book Interconnections, Bridges and Routers, published by Addison Wesley Publishing Company, in 1992, all disclosures of which are incorporated herein by reference, particularly at pages 33-34. As explained by Perlman at page 34, LLC type 2 reliable communication makes use of four packet types: I packets; RR packets; RNR packets; and, REJ packets:
xe2x80x9c1. I (stands for xe2x80x9cinformationxe2x80x9d) is a data packet. In this case, the CTL [control] field is 2 bytes long and includes 7 bits of sequence number for the data packets being transmitted from source S to destination D, plus 7 bits sequence number for the acknowledgment for packets being received from D by S.
2. RR (xe2x80x9creceive readyxe2x80x9d) is an acknowledgment. It contains a sequence number and indicates that all packets with sequence numbers lower than that have been received. It also indicates that the receiver is prepared to receive more data.
3. RNR (xe2x80x9creceive not readyxe2x80x9d) is an acknowledgment for previously transmitted packets (with numbers lower than the sequence number in the receive sequence number field in the RNR), just like the RR. However, it also indicates that the receiver is temporarily busy and that further packets should not be transmitted until the receiver indicates it can accept new packets, by transmitting an RR.
4. REJ (xe2x80x9crejectxe2x80x9d) indicates that the receiver is requesting retransmission of packets starting with the number in the receive sequence number field.xe2x80x9d
An ACK timer in the source station is started each time transmission of a sequence of packets is begun by the source station, and the ACK timer expires after an xe2x80x9cACK timing intervalxe2x80x9d. The source station anticipates receiving a response frame (that is, an ACK message), for example a Receive/Ready (RR) frame, acknowledging that the destination station received the preceding sequence of frames. In the absence of receipt of an RR frame during the ACK timing interval, the ACK timer expires and the source station transmits a xe2x80x9cpollxe2x80x9d frame in order to seek a response from the destination station to indicate whether or not the destination station is still active on the network. Reliable communication of LLC type 2 is described by Andrew Tanenbaum in his book Computer Networks, Second Edition, published in 1988, all disclosures of which are incorporated herein by reference, especially at pages 253-257.
However a problem arises when the link round trip time is substantially equal to, or longer than, the ACK timing interval of the ACK timer. The ACK timer may expire before the response, for example the RR frame, is received by the source station. Factors delaying the response frame comprise: the response frame is still on its way from the destination station back to the source station; the frame transmitted by the source station has not reached the destination station because it is stuck in a queue of an intermediate router experiencing congestion; the outgoing frame is still stuck in a queue in the source station and has not been transmitted because the network connected to the source station is congested; etc.
Historically, LLC type 2 reliable communication was introduced to operate over a SRB network where the delays are small and predictable. However, further developments introduced wide area network links into SRB networks having LLC type 2 reliable communication, and so introduced long and variable packet travel times. The long and variable packet travel times give rise to premature expiration of the ACK timer in the LLC type 2 reliable communication protocol.
The premature expiration of the ACK timer causes the source station to transmit a poll frame requesting a response from the destination station. The destination station then receives the poll frame and transmits an acknowledgment response to the poll frame, for example another RR frame. Accordingly, the source station receives two (2) RR acknowledgment frames in succession from the destination station, the first from the properly received sequence of information frames and the second in response to the poll frame. Receipt of two (2) RR acknowledgment frames in succession by a source station is a violation of IEEE 802.2 protocol rules. The violation of the protocol rules causes the source station to terminate the session. Termination of the session due to an inadvertent time-out of the ACK timer is a great inconvenience for users of the network. Presently, the ACK timing interval is manually configured in order to account for low bandwidth communication sessions in the network.
The problem of termination of the session upon receipt by a station of two successive acknowledgment frames remains in the Standard ISO/IEC 8802-2:1988, ANSI/IEEE Std. 802.2, 1998 Edition, (IEEE 802.2) at clause 5.4.2.3.5 xe2x80x9cFrame Reject (FRMR) Responsexe2x80x9d, as follows:
xe2x80x9cThe FRMR (frame reject response) PDU (protocol data unit) shall be used by the LLC in the asynchronous balanced mode (two way communication) to report the observance of a condition, that is not correctable by re-sending the identical PDU, that resulted from the receipt of a PDU from the remote LLC . . . The FRMR response PDU may be used in the case of any or both of the following conditions: The receipt of an unsolicited F bit set to xe2x80x9c1xe2x80x9d (that is, two ACK messages in succession) . . . The LLC receiving the FRMR response PDU shall pass a DL-RESET indication primitive to the network layer, which is responsible itself for initiating the appropriate mode setting or resetting corrective action by instructing the LLC to initialize both directions of information transfer on the data link connection, using the SABME (set asynchronous balanced mode extended) and DISC (disconnect) (the SABME and DISC commands end the session and a new session must then be established) command PDUs, as applicable.xe2x80x9d
Also, the IEEE 802.2 Standard at clause 7.7 xe2x80x9cFRMR Exception Conditionsxe2x80x9d, action of resetting the session upon receipt of a FRMR response PDU is defined as the LLC layer passing a message up the protocol stack to its supervisory mechanism in the network layer.
The expiration of an ACK timer in the source station for long distance transmissions over Wide Area Networks (WANs) using the TCP/IP protocol has been addressed. Particularly, the use of a time out and retransmission timer using the TCP/IP protocol for WANs is described by Douglas E. Comer in his book xe2x80x9cInternetworking with TCP/IPxe2x80x9d, 3rd edition, Vol. 1, published by Prentice-Hall in 1995, all disclosures of which are incorporated herein by reference, particularly at pages 208-216. The TCP/IP protocol is designed for communication over long distances of a Wide Area Network (WAN). There can be large variations in the time required for a packet to travel across a WAN, and Comer shows, at his page 210, sample measurements for Internet round trip times measured for 100 successive IP datagrams traveling across the global Internet; the trip times appear to vary from less than two seconds to more than eight seconds for this particular set of 100 successive IP datagrams.
The TCP/IP protocol is in the transport layer of the Internet model protocol, and also in the OSI communication reference model. The communications reference models are discussed by Andrew S. Tanenbaum in his book xe2x80x9cComputer Networks, 3rd editionxe2x80x9d, published by Prentice-Hall, PTR in 1996, all disclosures of which are incorporated herein by reference, particularly at pages 28-54. In the Internet, or TCP/IP reference model, the layers of the communications reference model comprise: the physical layer at layer 1; above that is layer 2 including the MAC address and, for SRB networks, RIF information; next higher is layer 3 that is the Internet, or IP, layer which provides best effort packet (or datagram) communication; and above that the transport, or TCP, layer 4 which provides reliable communication.
The problem of premature timeout in LLC type 2 reliable transport was addressed by development of the data link switching protocol, DLSw, as explained in RFC 1795 (Internet Engineering Task Force, xe2x80x9cIETFxe2x80x9d, Request For Comments, Informational RFC, RFC 1795, dated April 1995, www.ietf.org), which in Section 2, in relevant part states:
xe2x80x9cData Link Switching was developed to provide support for SNA and NetBIOS in multi-protocol routers. Since SNA and NetBIOS are basically connection oriented protocols, the Data Link Control procedure that they use on the LAN is IEEE 802.2 Logical Link Control (LLC) Type 2. Data Link Switching also accommodates SNA protocols over WAN (Wide Area Network) links via the SDLC [Synchronous Data Link Control] protocol.
IEEE 802.2 LLC Type 2 was designed with the assumption that the network transit delay would be predictable (i.e., a local LAN). Therefore the LLC Type 2 elements of procedure use a fixed timer for detecting lost frames. When remote bridging is used over wide area lines (especially at lower speeds), the network delay is larger and it can vary greatly based upon congestion. When the delay exceeds the time-out value LLC Type 2 attempts to retransmit. If the frame is not actually lost, only delayed, it is possible for the LLC Type 2 procedures to become confused. And as a result, the link may be eventually taken down if the delay exceeds the T1 timer times N2 retry count.xe2x80x9d
The solution offered by the DLSw protocol option in RFC 1795 is to package the LLC type 2 frames into TCP/IP for transport across a wide area network, or across a slow link. RFC 1795 defines Switch to Switch Protocol (SSP) frame formats to accomplish encapsulating LLC type 2 frames into TCP/IP. Packaging the LLC type 2 frames into TCP/IP packets reduces the size of the network domain over which LLC type 2 reliable transport is implemented, and so shortens the time interval which the source end station must wait before receiving an LLC type 2 acknowledgment message in a return frame. However, the fundamental problem of premature timeout in LLC type 2 reliable transport is not addressed by the DLSw option, and in fact is simply avoided.
Further, some network designs require LLC type 2 reliable communication from end station to end station, without a DLSw link. In these designs the problem of premature expiration of the ACK timer remains a problem, especially where WAN links or congested intermediate routers or bridges are included within the span of the LLC type 2 reliable communication.
There is needed a mechanism to prevent inadvertent time-outs of the ACK timer in communications between a source station and destination station using LLC type 2 reliable transport, especially when a slow link is employed for the connection, and also when the session bandwidth is subject to dynamic variations during day to day operations.
A method for computing an ACK timing interval for an ACK timer in a protocol layer LLC type 2 session first measures a time interval between transmission of a frame by a source computer joined to a destination computer by an intermediate link, and receipt of a corresponding acknowledgment frame by the source computer from the destination computer. The two events at the source computer: i.e., starting a timer upon commencement of transmission of a frame or sequence of frames and the later reception of an acknowledge message indicating receipt of those frames, permits calculation of a measured time interval. The measured time interval is used to dynamically compute the bandwidth of the intermediate link. The required ACK timing interval for the next ACK timer is then computed in response to the dynamically computed bandwidth and the number of bytes to be transmitted and subsequently acknowledged. The ACK timing interval may be recomputed after every transmission of frames and receipt of a corresponding ACK message. The ACK timing interval is thereby dynamically adjusted to conditions on the intermediate link, including natural bandwidth for either a slow or fast link, congestion due to other traffic on the link, etc. The dynamic adjustment of the ACK timing interval prevents inadvertent timeouts of the ACK timer, and so prevents inadvertent breaking of the LLC type 2 reliable transport connection.
Other and further aspects of the present invention will become apparent during the course of the following description and by reference to the accompanying drawings.